﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PrimaryAlgorithm.SortedArrayToBST
{
    /// <summary>
    /// 将有序数组转换为二叉搜索树
    /// </summary>
    class MainProject
    {
        static void Main(string[] args)
        {
            int[] nums = new int[] { -10,-3,0,5,9 };
            TreeNode treeNode = new TreeNode(1, new TreeNode(2, new TreeNode(3), new TreeNode(5)), new TreeNode(2, new TreeNode(4), new TreeNode(3)));
            Console.WriteLine(SortedArrayToBST(nums));
            Console.ReadKey();
        }
        public static TreeNode SortedArrayToBST(int[] nums)
        {
            if (nums.Length<=0)
            {
                return null;
            }
            int rootIndex = nums.Length/2;
            TreeNode root = new TreeNode(nums[rootIndex]);
            DFS(nums, 0, rootIndex, root, 1);
            DFS(nums, rootIndex+1, nums.Length, root,2);
            return root;



        }


        public static void DFS(int[] nums, int left, int last, TreeNode treeNode,int flag)
        {
            if (left == last)
            {
                return;
            }
            int index = (left+ last)/2;
            TreeNode treeNode1 = null;
            if (flag==1)
            {
                //可以用返回值的方式解决
                treeNode.left = new TreeNode(nums[index]);
                treeNode1 = treeNode.left;
            }
            else
            {
                treeNode.right = new TreeNode(nums[index]);
                treeNode1 = treeNode.right;
            }
            DFS(nums, left, index, treeNode1,1);
            DFS(nums, index + 1, last, treeNode1,2);
        }
    }
}
